//
// Source code recreated from a .class file by IntelliJ IDEA
// (powered by FernFlower decompiler)
//

package 力扣.题库.未分类.demo1AND20;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Objects;

public class demo15 {
    public demo15() {
    }

    public static void main(String[] args) {
        int[] nums = new int[]{3, 0, -2, -1, 1, 2};
        new ArrayList();
        List<List<Integer>> res = threeSum(nums);
        System.out.println(res);
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();

        //1.排序
        Arrays.sort(nums);

        //2.遍历
        for(int i = 0 ; i < nums.length ;i++){
            //首先，确定寻找以num[i]开始的组合

            //因为已经有序，以组合以 正数开始的，肯定就排除了,直接结束
            if(nums[i] > 0) break;

            //去重条件:排除重复组合
            if(i > 0 && nums[i] == nums[i - 1]) continue;


            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[i] + nums[left] + nums[right] == 0){
                    List<Integer> item = new ArrayList<>();
                    item.add(nums[i]);
                    item.add(nums[left]);
                    item.add(nums[right]);
                    res.add(item);

                    //找到一个组合后，就要继续寻找 ，判断有没有不同组合
                    //做去重处理--- 跳过 和左边界相邻的重复元素，和右边界相邻的重复元素
                    while(left < right && nums[left] == nums[left + 1]) left++;
                    while(left < right && nums[right] == nums[right - 1])  right--;

                }

                if(nums[i] + nums[left] + nums[right] < 0){

                    left++;
                }else{

                    right--;
                }

            }

        }
        return res;
    }
}
